package 题目集.滑动窗口.ch01_定长窗口;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/maximum-number-of-occurrences-of-a-substring/description/
 * 题意：一个字串s，最大和最小窗口长度maxS，minS，以及窗口内最多的种类数maxType
 * 问 在窗口符合maxS和minS，且窗口内字符种类数<=maxType。出现最多的字符串出现了多少次
 */
public class ch03_子串的最大出现次数 {

    /**
     * 思路：滑动窗口模拟
     */
    public int maxFreq(String s, int maxType, int minSize, int maxSize) {
        char[] chars = s.toCharArray();
        int ans = 0;
        int type = 0;   //窗口内的字符种类
        Map<String, Integer> map = new HashMap<>(); //每个符合条件字符串出现的次数
        int[] cnt = new int[128];    //每个字符在窗口内出现的次数
        for (int l = 0, r = 0; r < chars.length; r++) {
            if (cnt[chars[r]]++ == 0) type++;
            //先保证符合窗口限制
            while (type > maxType || r - l + 1 > maxSize) {
                cnt[chars[l]]--;
                if (cnt[chars[l++]] == 0) type--;
            }
            /**
             * 下面这个点有点绕，需要多想。
             * 在符合窗口的情况下，我们只需要管大小为minSize的。
             * 为什么？
             * 思考个问题：如果abc符合条件，bc也符合条件,我们需要保留abc吗？
             * 什么情况下要保留abc？abc是潜力股，它可能在某一天超过bc。那么我们才要保留abc
             *
             * 那么在这个问题中,abc可能比bc更有潜力吗？
             * 不会，因为如果最终结果包含abc，那么它也一定包含bc，所以bc的潜力>=abc的潜力
             */
            while (r - l + 1 > minSize) {
                cnt[chars[l]]--;
                if (cnt[chars[l++]] == 0) type--;
            }
            if (r - l + 1 == minSize) {
                String temp = s.substring(l, r + 1);
                map.put(temp, map.getOrDefault(temp, 0) + 1);
                cnt[chars[l]]--;
                if (cnt[chars[l++]] == 0) type--;
            }
        }
        for (Integer c : map.values()) {
            ans = Math.max(c, ans);
        }
        return ans;
    }

    @Test
    public void t1() {
        String s = "abcde";
        int cnt = maxFreq(s, 2, 3, 3);
        System.out.println(cnt);
    }

    @Test
    public void t2() {
        String s = "aababcaab";
        int cnt = maxFreq(s, 2, 3, 4);
        System.out.println(cnt);
    }

}
